package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/taking-maximum-energy-from-the-mystic-dungeon/description/?envType=daily-question&envId=2025-10-10
 * @create 2025/10/10 10:46
 * @since JDK17
 */

public class Solution09 {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length, ans = Integer.MIN_VALUE;
        int[] dp = new int[n];
        for (int i = n - k; i < n; i++) {
            dp[i] = energy[i];
            ans = Math.max(ans, dp[i]);
        }

        for (int i = n - k - 1; i >= 0; i--) {
            dp[i] = energy[i] + dp[i + k];
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
